1. Field of the Invention
The invention relates in general to the technical domain of algorithms efficiently executable by an automatic processor and more especially to an improved algorithm for modular inversion. The invention is particularly suitable for cryptographic applications, as occur, for example, in connection with smart cards.
2. Description of the Related Art
In the field of cryptography methods for modular inversion are employed, for example, in the generation of a pair of keys for the RSA encoding and signature method described in U.S. Pat. No. 4,405,829. The RSA method uses a public key (E, N) and a secret private key R, wherein the value N is the product of two large prime numbers P and Q. For calculating the pair of keys the values P, Q and E are first established. The private key R is then calculated as the modular inverse of the value E in relation to the module M with M=(P−1)·(Q−1).
In general, for two given whole numbers E and M the modular inverse of the value E in relation to the module M is defined as the number R to which 0≦R<M and 1=E·R mod M applies; the result R is also designated by 1/E. A modular inverse R exists if E and M are relatively prime.
Algorithms for calculating the modular inverse of a given value E in relation to a given module M are known per se. For example, the use of the extended Euclidian algorithm for modular inversion is described on pages 47 and 67 of the book by J. v. z. Gathen and J. Gerhard, “Modern Computer Algebra”, first edition, Cambridge University Press, 1999 (algorithm 3.6 and theorem 4.1). A small increase in efficiency in the application example of RSA key pair calculation is possible by a transformation according to the Chinese remainder theorem. A modification of the extended Euclidian algorithm, particularly advantageous in connection with binary numbers, is Stein's method, described on pages 321 to 324 of the book by Donald E. Knuth, “The Art of Computer Programming”, Vol. 2, second edition, Addison-Wesley, 1981, in connection with exercise 35 on page 339 and the solution thereto on page 606.
The methods for modular inversion mentioned are, however, relatively expensive in terms of computing. They require several times the computing time of other elementary modular computing operations, such as, e.g. modular multiplication (see page 304, corollary 11.6 of said book by Gathen and Gerhard). This is particularly problematic if the modular inversion is to be executed by a processor with relatively low power, as is the case, for example, in the processor of a smart card or some other portable data carrier.